<?php
/**
 * Created by PhpStorm.
 * Date: 2016/7/4
 * Time: 14:52
 */

/*
*	冒泡
*/
function  mpSort($arr)
{
	$count = count($arr);
	for($i=0;$i<$count;$i++)
	{
		for($j=0;$j<($count-$i-1);$j++)
		{
			if($arr[$j+1]<$arr[$j])
			{
				$tmp		=	$arr[$j+1];
				$arr[$j+1]	=	$arr[$j];
				$arr[$j]	=	$tmp;
			}
		}

	}
	return $arr;
}


/**
*	快排
*/

function quickSort($arr)
{
	$count = count($arr);
	if($count>1){
		$start = $arr[0];
		$left  = array();
		$right = array();
		for($i=1;$i<$count;$i++)
		{
			if($arr[$i]>=$arr[$position])
			{
				$right[] = $arr[$i];
			}else{
				$left[]  = $arr[$i];
			}
		}

			$left = quickSort($left);
			$right= quickSort($right);
		
		$left[]	=	$start;
		for($k=0;$k<count($right);$k++)
		{
			$left[]=$right[$k];
		}
		return $left;
	}else{
		return $arr;
	}
}

/*
*	大数相加
*/

function lAdd($a,$b)
{
	$a	= (string)$a;
	$b	= (string)$b;
	$la	= strlen($a);
	$lb	= strlen($b);
	if($la>=$lb)
	{
		$result='';
		$tmp = 0;
		$carry=0;
		for($i=0;$i<$la;$i++)
		{
			if($i<$lb)
			{
				$tmp=$a[$la-$i-1]+$b[$lb-$i-1]+$carry;
			}else{
				$tmp=$a[$la-$i-1]+$carry;
			}		
			if($tmp>9)
			{
				$carry=1;
				$tmp=(string)$tmp;				
				$tmp=$tmp[1];
			}else{
				$carry=0;
			}
			$result.=$tmp;
		}
		if($carry!=0){
			$result.=$carry;
		}
	}else{
		return lAdd($b,$a);
	}
	return strrev($result);
}

/*
*	大位数相乘
*/
function lMultiply($a,$b)
{
	$a=ltrim((string)$a,'0');
	$b=ltrim((string)$b,'0');
	$la	= strlen($a);
	$lb	= strlen($b);
	if($la>=$lb){
		$return=0;
		for($i=0;$i<$lb;$i++)
		{
			$tmp=$b[$lb-1-$i];
			if($tmp==0)
			{
				$g=1;
			}else{
				for($k=1;$k<$tmp;$k++)
				{
					if($k==1)
					{
						$result = $a;
					}
					$result = lAdd($result,$a);
				}
				$zero='';
				for($m=0;$m<$i;$m++){
					$zero.='0';
				}
				$result.=$zero;
				$return = lAdd($return,$result);
			}

		}
	}else{
		return 	lMultiply($b,$a);	
	}
	return $return;
}

/**
*	插入排序
*/
function insertSort($arr)
{
	$left	=	array();
	$left[] =   $arr[0];
	unset($arr[0]);
	$count	=	count($arr);	
	for($i=1;$i<$count+1;$i++)		
	{	
		$flag=0;
		$lcount = count($left);
		for($j=0;$j<$lcount;$j++)
		{
			if($arr[$i]<=$left[$j])
			{
				$left=shiftArray($left,$arr[$i],$j);
				$flag=1;
				break;
			}
		}
		if($flag!=1)
		{
			$left[]=$arr[$i];
		}
	}
	return $left;
}

/**
*	向数组头部插入元素
*/
function shiftArray($arr,$item,$position=0)
{
	$count = count($arr);
	for($i=$count-1;$i>$position-1;$i--)
	{
		$arr[$i+1]=$arr[$i];
	}
	$arr[$position]=$item;
	return $arr;
}

/*
*	选择排序
*/
function selectSort($arr)
{
	$count	=	count($arr);
	$sorted	=	array();
	$tmp	=	$arr[0];
	$flag   =   0;
	while($count>0)
	{
		if($flag == 1){
			unset($arr);
			$arr = $left;
			unset($left);
			$tmp=$arr[0];
		}		
		for($i=1;$i<$count;$i++)
		{
			if($tmp>$arr[$i]){
				$left[]=$tmp;
				$tmp=$arr[$i];
			}else{
				$left[]=$arr[$i];
			}
		}
		$sorted[]=$tmp;	
		$flag=1;
		$count--;
	}
	return $sorted;
}

/**
*	根据key删除数组元素并后移
*/
function deleteItem($arr,$key)
{
	$count = count($arr);
	$flag  = 0;
	for($i=0;$i<$count;$i++)
	{
		if($i==$key&&$flag==0)
		{
			unset($arr[$key]);
			$count--;
			$flag=1;
		}
		if($flag==1){
			$arr[$i] = $arr[$i+1];
		}
	}
	unset($arr[$count-1]);
	return $arr;
}

/*
*	归并排序
*/
function mergeSort($arr)
{
	$count	=	count($arr);
	if($count<2)
	{
		//var_dump($arr);
		return $arr[0];
	}
	for($i=0;$i<$count;$i++)
	{
		$flag	=	$i % 2;
		if($flag == 1)
		{
			$tmp[]		=	$arr[$i];
			$return[]	=	compareArr($tmp);
			$tmp		=	array();
		}else{
			$tmp[]		=	$arr[$i];
		}
	}
	if(count($tmp)>0)
	{
		$return[]	=	$tmp[0];
	}
	return 	mergeSort($return);	
}

/*
*	比较大小【辅助归并排序】
*/
function compareArr($arr)
{
	$return	=	array();
	$left	=	$arr[0];
	$right	=	$arr[1];
	$lCount	=	count($left);
	$rCount	=	count($right);
	if($lCount==1)
		$left	=	(array)$left;
	if($rCount==1)
		$right	=	(array)$right;
	
	$i		=	0;
	$j		=	0;
	while($lCount>$i && $rCount>$j)
	{
		$tmpLeft	=	$left[$i];
		$tmpRight	=	$right[$j];
		if($tmpLeft<$tmpRight)
		{
			$return[]	=	$tmpLeft;
			++$i;
		}else{
			$return[]	=	$tmpRight;
			++$j;	
		}
	}	
	if($i<$lCount)
	{
		for($k=$i;$k<$lCount;$k++)
		{
			$return[]	=	$left[$k];
		}
	}else{
		for($k=$j;$k<$rCount;$k++)
		{
			$return[]	=	$right[$k];
		}
	}
	return $return;
}
/*
$a	=	range(1,20);
shuffle($a);
var_dump(mergeSort($a)); 
*/

/*
*	基数排序
*/
function base_sort(&$arr){
	$len=count($arr);
	$max=0;
	$cnt=0;
	$arr_=array();
	for($i=0;$i<$len;$i++)        //获取数组中的最大值
		if($arr[$i]>$max)
			$max=$arr[$i];
	while($max/10!=0){        //获取最大值一共有多少位，以便于以后决定进行多少次入桶和出桶
		$max=(int)$max/10;
		$cnt++;
	}
	$cnt--;
	for($i=0;$i<$cnt;$i++){
		$temp=pow(10,$i);
		for($j=0;$j<$len;$j++){        //将每一个元素进行入桶
			$a=$arr[$j]/$temp%10;
			echo $a.'<br />';
			$arr_[$a][]=$arr[$j];
		}
		for($arr_index=0,$k=0;$k<10;$k++){     
			if(isset($arr_[$k])){//将每一个元素进行出桶，并将他们进行合并
				for($j=0;$j<count($arr_[$k]);$j++){
					$arr[$arr_index++]=$arr_[$k][$j];			
				}
			}
		}
		unset($arr_);
	}
}